{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Rounding Error to Meet Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化舍入误差以满足目标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一系列价格&nbsp;<code>[p<sub>1</sub>,p<sub>2</sub>...,p<sub>n</sub>]</code>&nbsp;和一个目标&nbsp;<code>target</code>，将每个价格&nbsp;<code>p<sub>i</sub></code>&nbsp;舍入为&nbsp;<code>Round<sub>i</sub>(p<sub>i</sub>)</code>&nbsp;以使得舍入数组&nbsp;<code>[Round<sub>1</sub>(p<sub>1</sub>),Round<sub>2</sub>(p<sub>2</sub>)...,Round<sub>n</sub>(p<sub>n</sub>)]</code>&nbsp;之和达到给定的目标值&nbsp;<code>target</code>。每次舍入操作&nbsp;<code>Round<sub>i</sub>(p<sub>i</sub>)</code>&nbsp;可以是向下舍&nbsp;<code>Floor(p<sub>i</sub>)</code>&nbsp;也可以是向上入&nbsp;<code>Ceil(p<sub>i</sub>)</code>。</p>\n",
    "\n",
    "<p>如果舍入数组之和无论如何都无法达到目标值&nbsp;<code>target</code>，就返回字符串&nbsp;<code>\"-1\"</code>。否则，以保留到<strong>小数点后三位</strong>的字符串格式返回最小的舍入误差，其定义为 <code>Σ |Round<sub>i</sub>(p<sub>i</sub>) - (p<sub>i</sub>)|</code>（&nbsp;i 从 1 到 n ）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [\"0.700\",\"2.800\",\"4.900\"], target = 8\n",
    "<strong>输出：</strong>\"1.000\"\n",
    "<strong>解释： </strong>\n",
    "使用 Floor，Ceil 和 Ceil 操作得到 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [\"1.500\",\"2.500\",\"3.500\"], target = 10\n",
    "<strong>输出：</strong>\"-1\"\n",
    "<strong>解释：</strong>\n",
    "达到目标是不可能的。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [\"1.500\",\"2.500\",\"3.500\"], target = 9\n",
    "<strong>输出：</strong>\"1.500\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 500</code></li>\n",
    "\t<li>表示价格的每个字符串&nbsp;<code>prices[i]</code>&nbsp;都代表一个介于 <code>[0.0,&nbsp;1000.0]</code> 之间的实数，并且正好有 3 个小数位。</li>\n",
    "\t<li><code>target</code>&nbsp;介于&nbsp;0 和 1000000&nbsp;之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-rounding-error-to-meet-target](https://leetcode.cn/problems/minimize-rounding-error-to-meet-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-rounding-error-to-meet-target](https://leetcode.cn/problems/minimize-rounding-error-to-meet-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"0.700\",\"2.800\",\"4.900\"]\\n8', '[\"1.500\",\"2.500\",\"3.500\"]\\n10', '[\"1.500\",\"2.500\",\"3.500\"]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        decimal = []\n",
    "\n",
    "        for p in prices:\n",
    "            num = float(p)\n",
    "            left += math.floor(num)\n",
    "            right +=math.ceil(num)\n",
    "            decimal.append(num%1)\n",
    "        if left<=target<=right:\n",
    "            decimal.sort()\n",
    "            num_ceil = target-left\n",
    "            res = sum(decimal[:-num_ceil])+ num_ceil-sum(decimal[-num_ceil:])\n",
    "            return f'{abs(res):.03f}'\n",
    "        else:\n",
    "            return '-1'\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        decimal = []\n",
    "\n",
    "        for p in prices:\n",
    "            num = float(p)\n",
    "            left += math.floor(num)\n",
    "            right +=math.ceil(num)\n",
    "            decimal.append(num%1)\n",
    "        if left<=target<=right:\n",
    "            decimal.sort()\n",
    "            num_ceil = target-left\n",
    "            res = sum(decimal[:-num_ceil])+ num_ceil-sum(decimal[-num_ceil:])\n",
    "            return f'{abs(res):.03f}'\n",
    "        else:\n",
    "            return '-1'\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for price in prices:\n",
    "            price = float(price)\n",
    "            cur += int(price)\n",
    "            add = price - int(price)\n",
    "            if add > 0:\n",
    "                ans.append(add)\n",
    "\n",
    "        if target < cur or target > cur + len(ans):\n",
    "            return \"-1\"\n",
    "\n",
    "        gap = target - cur\n",
    "        ans.sort(reverse=True)\n",
    "        rest = gap - sum(ans[:gap]) + sum(ans[gap:])\n",
    "        return \"%.3f\" % rest\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "        total, n = 0, len(prices)\n",
    "        floats = []\n",
    "        zeros = 0\n",
    "        for num in prices:\n",
    "\n",
    "            numi, numf = num.split('.')\n",
    "            if int(numf) == 0:\n",
    "                zeros += 1\n",
    "            floats.append(int(numf))\n",
    "            total += int(numi)\n",
    "        \n",
    "        if not (total <= target <= total + n - zeros):\n",
    "            return \"-1\"\n",
    "\n",
    "        floats.sort(key=lambda x: 1000-2 * x)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i < target - total:\n",
    "                ans += 1000 - floats[i]\n",
    "            else:\n",
    "                ans += floats[i]\n",
    "        ans = str(ans)\n",
    "        if len(ans) <= 3:\n",
    "            while len(ans) < 3:\n",
    "                ans = \"0\" + ans\n",
    "            ans = \"0.\" + ans\n",
    "        else:\n",
    "            ans = ans[:-3] + \".\" + ans[-3:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "        ans = []\n",
    "        floor_sum = 0\n",
    "\n",
    "        for price in prices:\n",
    "            price = float(price)\n",
    "            floor_sum += int(price)\n",
    "            diff = price - int(price)\n",
    "\n",
    "            if diff > 0:\n",
    "                ans.append(diff)\n",
    "        \n",
    "        if target < floor_sum or target > floor_sum + len(ans):\n",
    "            return \"-1\"\n",
    "        \n",
    "        gap = target - floor_sum\n",
    "        ans.sort(reverse=True)\n",
    "        result = gap - sum(ans[:gap]) + sum(ans[gap:])\n",
    "\n",
    "        return \"{:.3f}\".format(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def minimizeError(self, prices: List[str], target: int) -> str:\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for price in prices:\n",
    "            price = float(price)\n",
    "            cur += int(price)\n",
    "            add = price - int(price)\n",
    "            if add > 0:\n",
    "                ans.append(add)\n",
    "\n",
    "        if target < cur or target > cur + len(ans):\n",
    "            return \"-1\"\n",
    "\n",
    "        gap = target - cur\n",
    "        ans.sort(reverse=True)\n",
    "        rest = gap - sum(ans[:gap]) + sum(ans[gap:])\n",
    "        return \"%.3f\" % rest\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
